Write a program to solve a Sudoku puzzle by filling the empty cells.
A sudoku solution must satisfy all of the following rules:
- Each of the digits
1-9 must occur exactly once in each row.
- Each of the digits
1-9 must occur exactly once in each column.
- Each of the digits
1-9 must occur exactly once in each of the 9 3x3 sub-boxes of the grid.
The '.' character indicates empty cells.
Example 1:
Input: board = [["5","3",".",".","7",".",".",".","."],["6",".",".","1","9","5",".",".","."],[".","9","8",".",".",".",".","6","."],["8",".",".",".","6",".",".",".","3"],["4",".",".","8",".","3",".",".","1"],["7",".",".",".","2",".",".",".","6"],[".","6",".",".",".",".","2","8","."],[".",".",".","4","1","9",".",".","5"],[".",".",".",".","8",".",".","7","9"]]
Output: [["5","3","4","6","7","8","9","1","2"],["6","7","2","1","9","5","3","4","8"],["1","9","8","3","4","2","5","6","7"],["8","5","9","7","6","1","4","2","3"],["4","2","6","8","5","3","7","9","1"],["7","1","3","9","2","4","8","5","6"],["9","6","1","5","3","7","2","8","4"],["2","8","7","4","1","9","6","3","5"],["3","4","5","2","8","6","1","7","9"]]
Explanation: The input board is shown above and the only valid solution is shown below:
Constraints:
board.length == 9
board[i].length == 9
board[i][j] is a digit or '.'.
- It is guaranteed that the input board has only one solution.
Submissions:
Status
Submission time (YYYY-MM-DD)
Language
Runtime
Memory
Code
Accepted
2023-01-18
C++
181 ms
45.3 MB
class Solution {
public:
int ans[9][9];
map> rowFreqMap;
map> colFreqMap;
map> boxFreqMap;
int box[9][9];
bool validNumberToPut(int row,int col,int num,map> &rowFreqMap,map> &colFreqMap,map> &boxFreqMap) {
return (rowFreqMap[row].find(num)==rowFreqMap[row].end() && colFreqMap[col].find(num)==colFreqMap[col].end() && boxFreqMap[box[row][col]].find(num)==boxFreqMap[box[row][col]].end());
}
bool fillSudoku(vector>& board,vector> blanks,int cur,int totalBlanks,
map> &rowFreqMap, map> &colFreqMap,map> &boxFreqMap) {
if(cur==totalBlanks) {
return true;
}
int curRow=blanks[cur].first;
int curCol=blanks[cur].second;
for(int i=1;i<=9;i++) {
if(validNumberToPut(curRow,curCol,i,rowFreqMap,colFreqMap,boxFreqMap)) {
rowFreqMap[curRow][i]++;
colFreqMap[curCol][i]++;
boxFreqMap[box[curRow][curCol]][i]++;
board[curRow][curCol]=char(i+'0');
bool ansFound=fillSudoku(board,blanks,cur+1,totalBlanks,rowFreqMap,colFreqMap,boxFreqMap);
if(ansFound) {
return true;
}
rowFreqMap[curRow].erase(i);
colFreqMap[curCol].erase(i);
boxFreqMap[box[curRow][curCol]].erase(i);
board[curRow][curCol]=0;
}
}
return false;
}
void solveSudoku(vector>& board) {
int i,j;
vector> blanks;
rowFreqMap.clear();
colFreqMap.clear();
boxFreqMap.clear();
memset(ans,0,sizeof(ans));
for(i=0;i<9;i++)
for(j=0;j<9;j++) {
if(board[i][j]!='.') {
rowFreqMap[i][board[i][j]-'0']++;
colFreqMap[j][board[i][j]-'0']++;
ans[i][j]=board[i][j]-'0';
}
if(board[i][j]=='.')
blanks.push_back({i,j});
}
int boxNo=1;
for(i=0;i<9;i+=3) {
for(j=0;j<9;j+=3) {
for(int k=0;k<3;k++)
for(int l=0;l<3;l++) {
box[k+i][l+j]=boxNo;
if(board[k+i][l+j]!='.')
boxFreqMap[boxNo][ans[k+i][l+j]]++;
}
boxNo++;
}
}
fillSudoku(board,blanks,0,blanks.size(),rowFreqMap,colFreqMap,boxFreqMap);
}
};
class Solution {
public:
int ans[9][9];
map> rowFreqMap;
map> colFreqMap;
map> boxFreqMap;
int box[9][9];
bool validNumberToPut(int row,int col,int num,map> &rowFreqMap,map> &colFreqMap,map> &boxFreqMap) {
return (rowFreqMap[row].find(num)==rowFreqMap[row].end() && colFreqMap[col].find(num)==colFreqMap[col].end() && boxFreqMap[box[row][col]].find(num)==boxFreqMap[box[row][col]].end());
}
bool fillSudoku(vector>& board,vector> blanks,int cur,int totalBlanks,
map> &rowFreqMap, map> &colFreqMap,map> &boxFreqMap) {
if(cur==totalBlanks) {
return true;
}
int curRow=blanks[cur].first;
int curCol=blanks[cur].second;
for(int i=1;i<=9;i++) {
if(validNumberToPut(curRow,curCol,i,rowFreqMap,colFreqMap,boxFreqMap)) {
rowFreqMap[curRow][i]++;
colFreqMap[curCol][i]++;
boxFreqMap[box[curRow][curCol]][i]++;
board[curRow][curCol]=char(i+'0');
bool ansFound=fillSudoku(board,blanks,cur+1,totalBlanks,rowFreqMap,colFreqMap,boxFreqMap);
if(ansFound) {
return true;
}
rowFreqMap[curRow].erase(i);
colFreqMap[curCol].erase(i);
boxFreqMap[box[curRow][curCol]].erase(i);
board[curRow][curCol]=0;
}
}
return false;
}
void solveSudoku(vector>& board) {
int i,j;
vector> blanks;
rowFreqMap.clear();
colFreqMap.clear();
boxFreqMap.clear();
memset(ans,0,sizeof(ans));
for(i=0;i<9;i++)
for(j=0;j<9;j++) {
if(board[i][j]!='.') {
rowFreqMap[i][board[i][j]-'0']++;
colFreqMap[j][board[i][j]-'0']++;
ans[i][j]=board[i][j]-'0';
}
if(board[i][j]=='.')
blanks.push_back({i,j});
}
int boxNo=1;
for(i=0;i<9;i+=3) {
for(j=0;j<9;j+=3) {
for(int k=0;k<3;k++)
for(int l=0;l<3;l++) {
box[k+i][l+j]=boxNo;
if(board[k+i][l+j]!='.')
boxFreqMap[boxNo][ans[k+i][l+j]]++;
}
boxNo++;
}
}
fillSudoku(board,blanks,0,blanks.size(),rowFreqMap,colFreqMap,boxFreqMap);
}
};
Accepted
2023-01-18
C++
166 ms
45.2 MB
class Solution {
public:
int ans[9][9];
map> rowFreqMap;
map> colFreqMap;
map> boxFreqMap;
int box[9][9];
bool validNumberToPut(int row,int col,int num,map> &rowFreqMap,map> &colFreqMap,map> &boxFreqMap) {
return (rowFreqMap[row].find(num)==rowFreqMap[row].end() && colFreqMap[col].find(num)==colFreqMap[col].end() && boxFreqMap[box[row][col]].find(num)==boxFreqMap[box[row][col]].end());
}
bool fillSudoku(vector>& board,vector> blanks,int cur,int totalBlanks,
map> &rowFreqMap, map> &colFreqMap,map> &boxFreqMap) {
if(cur==totalBlanks) {
return true;
}
int curRow=blanks[cur].first;
int curCol=blanks[cur].second;
for(int i=1;i<=9;i++) {
if(validNumberToPut(curRow,curCol,i,rowFreqMap,colFreqMap,boxFreqMap)) {
rowFreqMap[curRow][i]++;
colFreqMap[curCol][i]++;
boxFreqMap[box[curRow][curCol]][i]++;
board[curRow][curCol]=char(i+'0');
bool ansFound=fillSudoku(board,blanks,cur+1,totalBlanks,rowFreqMap,colFreqMap,boxFreqMap);
if(ansFound) {
return true;
}
rowFreqMap[curRow].erase(i);
colFreqMap[curCol].erase(i);
boxFreqMap[box[curRow][curCol]].erase(i);
board[curRow][curCol]=0;
}
}
return false;
}
void solveSudoku(vector>& board) {
int i,j;
vector> blanks;
rowFreqMap.clear();
colFreqMap.clear();
boxFreqMap.clear();
memset(ans,0,sizeof(ans));
for(i=0;i<9;i++)
for(j=0;j<9;j++) {
if(board[i][j]!='.') {
rowFreqMap[i][board[i][j]-'0']++;
colFreqMap[j][board[i][j]-'0']++;
ans[i][j]=board[i][j]-'0';
}
if(board[i][j]=='.')
blanks.push_back({i,j});
}
// for(auto it: rowFreqMap) {
// cout<
class Solution {
public:
int ans[9][9];
map> rowFreqMap;
map> colFreqMap;
map> boxFreqMap;
int box[9][9];
bool validNumberToPut(int row,int col,int num,map> &rowFreqMap,map> &colFreqMap,map> &boxFreqMap) {
return (rowFreqMap[row].find(num)==rowFreqMap[row].end() && colFreqMap[col].find(num)==colFreqMap[col].end() && boxFreqMap[box[row][col]].find(num)==boxFreqMap[box[row][col]].end());
}
bool fillSudoku(vector>& board,vector> blanks,int cur,int totalBlanks,
map> &rowFreqMap, map> &colFreqMap,map> &boxFreqMap) {
if(cur==totalBlanks) {
return true;
}
int curRow=blanks[cur].first;
int curCol=blanks[cur].second;
for(int i=1;i<=9;i++) {
if(validNumberToPut(curRow,curCol,i,rowFreqMap,colFreqMap,boxFreqMap)) {
rowFreqMap[curRow][i]++;
colFreqMap[curCol][i]++;
boxFreqMap[box[curRow][curCol]][i]++;
board[curRow][curCol]=char(i+'0');
bool ansFound=fillSudoku(board,blanks,cur+1,totalBlanks,rowFreqMap,colFreqMap,boxFreqMap);
if(ansFound) {
return true;
}
rowFreqMap[curRow].erase(i);
colFreqMap[curCol].erase(i);
boxFreqMap[box[curRow][curCol]].erase(i);
board[curRow][curCol]=0;
}
}
return false;
}
void solveSudoku(vector>& board) {
int i,j;
vector> blanks;
rowFreqMap.clear();
colFreqMap.clear();
boxFreqMap.clear();
memset(ans,0,sizeof(ans));
for(i=0;i<9;i++)
for(j=0;j<9;j++) {
if(board[i][j]!='.') {
rowFreqMap[i][board[i][j]-'0']++;
colFreqMap[j][board[i][j]-'0']++;
ans[i][j]=board[i][j]-'0';
}
if(board[i][j]=='.')
blanks.push_back({i,j});
}
// for(auto it: rowFreqMap) {
// cout<